package me.zk.practice1.s;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;
import java.util.SortedMap;
import java.util.TreeMap;
import java.util.stream.Collectors;

/**
 * @Author: zhang kai
 * @Date: 2023/05/09
 * @Description:
 */
public class S17 {
    public static void main(String[] args) {

        System.out.println(Arrays.toString(topKFrequent(new int[]{1,1,1,1,2,2,2,3,4},2)));
    }
    public static int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (Integer num : nums) {
           map.put(num,map.getOrDefault(num,0)+1);
        }
        //将key根据value排序
        PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));
        for (Map.Entry<Integer,Integer> entry:map.entrySet()) {
            int num = entry.getKey(),count = entry.getValue();
            if (queue.size() == k) {
                if (queue.peek()[1] < count) {
                    queue.poll();
                    queue.offer(new int[]{num,count});
                }
            } else {
                queue.offer(new int[]{num,count});
            }
        }
        int[] ret = new int[k];
        for (int i = 0; i < k; i++) {
            ret[i] = queue.poll()[0];
        }
       return ret;
    }

    public static int[] topKFrequent1(int[] nums, int k) {
        SortedMap<Integer, Integer> sortedMap = new TreeMap<>();

        for (Integer num : nums) {
            if (sortedMap.containsKey(num)) {
                sortedMap.put(num,sortedMap.get(num) + 1);
            } else {
                sortedMap.put(num,1);
            }
        }
        Set<Map.Entry<Integer, Integer>> entry2 = sortedMap.entrySet();
        List<Map.Entry<Integer,Integer>> list =
                new ArrayList<>(entry2);

        Collections.sort(list, Map.Entry.comparingByValue((o1, o2) -> o2>o1 ? 1 : -1));
        List<Integer> keys = list.stream().map(Map.Entry::getKey).collect(Collectors.toList());

        int[] sortKeys = keys.stream().mapToInt(Integer::intValue).toArray();
        if (k > nums.length) {
            return sortKeys;
        }
        return keys.subList(0,k).stream().mapToInt(Integer::intValue).toArray();
    }
}
